This invention relates generally to the field of the design and manufacture of electronic devices, such as printed circuit boards and semiconductor devices, and more particularly to improvements in designing the wiring of a channel.
For the design of the wiring of a channel numerous approaches are known from the prior art. In the reference book by Naveed Sherwani, xe2x80x9cAlgorithms for VLSI Physical Design Automationxe2x80x9d, Second Edition, 1995, Kluwer Academic Publishers, an overview of prior art routing approaches is given, especially on pages 267 to 339.
One approach which is commonly used in the prior art for channel routing is the modeling of the routing problem by means of a vertical constraint graph. In a vertical constraint graph each net to be routed is represented by one node in the graph. If a vertical constraint exists between any terminal of a net and any terminal of another net the two corresponding nodes in the vertical constraints graph are connected by a directed edge in order to represent the vertical constraint. This way initially each net to be routed is assumed to be routable by just one horizontal trunk in the channel.
If any cycles exist in the vertical constraints graph these must be removed by a technique called xe2x80x9cdogleggingxe2x80x9d prior to the actual assignment of trunks. The doglegging technique is also described in the above cited reference by Naveed Sherwani, in Chapter 7.4.2.2, pages 299-301. A more detailed description of the doglegging technique is given in D. N. Deutsch,xe2x80x9cA dogleg channel routerxe2x80x9d, Proceedings of 13th ACM/IEEE Design Automation Conference, page 425-433, 1976 and in Preas, xe2x80x9cChannel Routing with Nonxe2x80x94Terminal Doglegsxe2x80x9d, Proceedings of the European Design Automation Conference, March 1990, Glasgow, UK, pages 451-458.
With reference to FIG. 1. a common prior art approach of using a vertical constraint graph and doglegging for channel routing is explained in more detail:
In step 100 all the terminals of the same net to be routed are logically unified into one single imaginary trunk in the channel. In step 102 a vertical constraints graph is built according to this abstraction.
In step 104 it is decided whether the vertical constraints graph built in step 102 has cycles. If no cycles exist this means that the channel can in fact be routed by making usage of the imaginary trunks as defined in step 100. In this case the trunks are in fact assigned to the channel in step 106 in order to produce the wiring layout.
If there are cycles in the vertical constraint graph the control goes from step 104 to step 108. In step 108 cycles in the vertical constraints graph are removed by means of doglegging. By doglegging the imaginary trunks as defined in step 100 are broken up into segments in order to remove conflicting vertical constraints. Next in step 106 the assignment of trunks to the channel is done.
The main disadvantages of this prior art approach are the computational requirements which increase by the power of four with the number of nets and the fact that it is not guaranteed thatxe2x80x94even after lengthy computationxe2x80x94all cycles can be removed in step 108 before the trunks are assigned to the channel for all classes of channel routing problems encountered in practice. Therefore a need exists for an enhanced method for designing and manufacturing an electronic device.
The underlying problem of the invention is solved basically by applying the features laid down in the independent claims. Preferred embodiments are given in the dependent claims.
The method of the invention is advantageous in that it allows the design and manufacture of an electronic apparatus, such as an integrated circuit chip or printed circuit board which has conflicting vertical constraints for which no solution could be found by any prior art design method.
The classes of problems which can be solved by the method of the invention include the following classes for which known prior art design methods fail:
1. Conflicting vertical constraints which can not be resolved by splitting of a node in the vertical constraints graph because splitting does not result in reducing the number of cycles; and
2. Conflicting vertical constraints which can not be resolved because splitting of the respective node does not create a cycle.
The invention is advantageous in that it uses a compositional approach. Initially all the terminals of the channel to be routed are represented individually in the terminal vertical constraints graph and also the vertical constraints which exist between individual terminals are represented in the terminal vertical constraint graph. This way the complete information about the routing problem to be solved is included in the terminal vertical constraint graph.
Further the compositional approach of the invention is advantageous in that it requires far less computing time; the computational requirements only increase with the power of three with the number of nets. Further, unnecessary computing time is saved because according to the invention the existence of a solution can be predicted at an early stage.
Further, the method of the invention can be applied under weaker restrictions as compared to the prior art so that the channel routing quality can be improved thereby.
This leads to the design and production of enhanced electronic devices which feature a more compact channel wiring design and therefore require less silicon floor space and less power dissipation. The more compact channel wiring design which results from the method of the invention also positively impacts signal propagation delays and therefore the overall operational speed of the electronic device and/or the electronic apparatus, such as a digital radio or audio device, in which it is integrated.
Further, the invention is advantageous in that it can be readily implemented by means of a computer program which is stored on an computer readable storage medium.